class Solution {
    //每次在上次能跳到的范围（end）内选择一个能跳的最远的位置（也就是能跳到max_far位置的点）作为下次的起跳点 
    public int jump(int[] nums) {
        //定义i之前的最远右边界
        int end = 0;
        //不断更新最远右边界
        int maxpos = 0;
        //记录跳跃次数
        int count = 0;
        for(int i = 0;i<nums.length-1;i++) {
            //找到下一个最远右边界
            maxpos = Math.max(maxpos,nums[i]+i);
            //到达最远右边界
            if(i == end) {
                end = maxpos;
                count++;
                if(end == nums.length-1) {
                    break;
                }
            }
        }
        return count;
    }
    public int jump1(int[] nums) {
        int[] dp = new int[nums.length+1];
        // 最后一个不处理

        for(int i = 1;i<nums.length;i++) {
            dp[i] = Integer.MAX_VALUE;
            for(int j = 0;j<i;j++) {
                if(j+nums[j] >= i) {
                    dp[i] = Math.min(dp[i],dp[j]+1);
                }
            }
        }
        return dp[nums.length-1];
    }
}